package piwan;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/** GroupManager keeps track of the connected components of the region graph, where "connected" means both adjacent and owned by the same player.
 * To update the components, the GameState class calls ownershipChanged() on regions whenever they change owners (be it because they've been chosen
 * by as a capital, or because they've been captured or abandoned in combat).
 * To get the connected groups, one needs to call getGroups() that has two version, one that returns _all_ groups and the other returns only groups
 * owned by a particular player.
 * The Group class wraps an ArrayList of regions that can be queried with the getRegions() method. One can also check whether a group contains a
 * capital.
 * 
 * @author Cristi Cobzarenco
 *
 */
public class GroupManager {
	private Group[] mapping = null;
	private ArrayList<Group> groups = new ArrayList<Group>();
	private World w;
	private void testIntegrity() {
		for(int i=0;i<mapping.length;++i) {
			if(mapping[i]!=null ){
				assert( mapping[i].regs.contains(w.getRegion(i)) ) : mapping[i] + " doesn't contain " + i;
			} else {
				for(Group g:groups) {
					assert(!g.regs.contains(w.getRegion(i))) : g + " contains null " + i;
				}
			}
		}
		
		for(Region r:w.getRegions()) {
			assert(!r.isOwned() || r.getSoldiers()>0);
		}
	}
	
	public class Group {
		private ArrayList<Region> regs = new ArrayList<Region>();
		private Player owner = null;
		private ArrayList<Polygon> polys = new ArrayList<Polygon>();
		private boolean polysNeedUpdate = false;
		private int capitals = 0;
		private int[] countRegs;
		private int[] countRscs;
		private int   soldsPerTurn = 0;
		private boolean doRecount = false; // also called the Florida variable :P
		
		/** Gets the owner of the regions in this group.
		 * 
		 * @return the player who owns this group
		 */
		public Player getOwner() {
			return owner;
		}
		
		/** Gets a polygon list that represents this group.
		 * 
		 * @return the polygon list
		 */
		public ArrayList<Polygon> getPolygons() {
			if(polysNeedUpdate)
				updatePolys();
			return polys;
		}
		
		/** Gets a list of all the regions in this group.
		 * 
		 * @return the region list.
		 */
		public ArrayList<Region> getRegions() {
			return regs;
		}
		
		/** Returns whether this group contains a capital or not.
		 * 
		 * @return true if the group contains a capital
		 */
		public boolean containsCapital() { return capitals>0; }
		
		/** Returns whether removing a soldier results into a region losing capital connection.
		 * 
		 * @param r region to test removal for
		 * @return result of test
		 */
		public boolean isUndoLegal(Region r) {
			regs.remove(r);
			mapping[r.getId()] = null;
			r.setOwner(null);
			boolean result = regroup(true);
			r.setOwner(owner);
			regs.add(r);
			mapping[r.getId()] = this;
			testIntegrity();
			return result;
		}
		
		public int getSoldiersPerTurn() { recount(); return soldsPerTurn; }
		public int getRegionTypeCount( RegionType rt ) { recount(); return countRegs[rt.getId()]; }
		public int getResourceCount(ResourceType rsc) { recount(); return countRscs[rsc.getId()]; }
		public int[] getResourceCounts() { recount(); return countRscs; }
		public int[] getRegionTypesCounts() { recount(); return countRegs; }
		public void addResourceCounts(int[] rs) {
			assert(rs.length==countRscs.length);
			recount();
			for(int i=0;i<rs.length;++i) rs[i] += countRscs[i];
		}
		public int getCapitalCount() { return capitals; }
		
		public void addRegionTypeCounts(int[] rs) {
			assert(rs.length==countRegs.length);
			recount();
			for(int i=0;i<rs.length;++i) rs[i] += countRegs[i];
		}
		
		/** Creates a new Group that contains one Region. The owner is set to that of the Region.
		 * It automatically adds itself to the GroupManager and updates the mapping for the Region.
		 * @param r the region to be added
		 */
		private Group(Region r) {
			countRegs = new int[w.getRegionTypeCount()];
			countRscs = new int[w.getResourceTypeCount()];
			
			owner = r.getOwner();
			assert(r.getOwner()!=null);
			groups.add(this);
			add(r);
		}
		
		/** Creates an empty Group, only to be used internally.
		 * 
		 * @param owner the owner of the group
		 */
		private Group(Player owner) {
			countRegs = new int[w.getRegionTypeCount()];
			countRscs = new int[w.getResourceTypeCount()];
			
			this.owner = owner;
			groups.add(this);
			doRecount=true;
		}
		
		/** Adds a new region to this group. Updates local list and mapping.
		 * 
		 * @param r region to be added
		 */
		private void add(Region r) {
			assert mapping[r.getId()]==null : "Region: "+r.getId();
			regs.add(r); // add it to the local reg list
			mapping[r.getId()] = this; // update the mapping
			polysNeedUpdate = true;
			doRecount = true;
			if(r.isCapital()) ++capitals;
		}
		
		/** Removes a region from this group. Updates local list and mapping. If the group becomes empty it removes itself from the GroupManager.
		 * 
		 * @param r region to remove 
		 */
		private void remove(Region r) {
			regs.remove(r); // remove it from the local reg list
			mapping[r.getId()] = null; // update the mapping
			
			if(regs.isEmpty())
				groups.remove(this);
			
			regroup(false);
			polysNeedUpdate = true;
			doRecount = true;
			testIntegrity();
		}
		
		
		/** Checks the connectivity of the group. If needed it creates new groups to accommodate unconnected components. Called after remove().
		 * It implements this as a BFS of the region graph, a standard algorithm for determining connected components of a graph. 
		 */
		private boolean regroup( boolean testCapital ) {
			
			// in case of a test this will hold the newly added groups
			ArrayList<Group> newgroups=null;
			// these regions which will be left unmapped after they're removed from this group
			ArrayList<Region> unmappeds = regs;
			// this queue is used for a BFS of the region graph
			Queue<Region> queue = new LinkedList<Region>();
			// the group we're adding regions now, start with this one, since we'll be reusing it
			Group curGroup;
			if(testCapital) {
				curGroup = null;
				newgroups = new ArrayList<Group>();
			} else
				curGroup = this;
			
			// clear the group for the regions
			for(Region r:regs)
				mapping[r.getId()]=null;
			
			// realloc the regs for this group to reuse it in the new grouping
			if(!testCapital) {
				regs = new ArrayList<Region>();
				capitals = 0;
			}
			
			// we go through all of the unmapped regions
			for(Region u: unmappeds ) {
				// add it to the queue (if it's already been traversed it'll be discarded in the do-loop
				if(getGroup(u) == null) {
					if(curGroup==null) {
						curGroup = new Group(owner);
						if(testCapital)
							newgroups.add(curGroup);
					}
					queue.add(u);
					do {
						Region r = queue.poll(); // get a region from the queue
						if(getGroup(r)==null) {
							curGroup.add(r); // map it to the current group
							for(Region adj: r.getAdjacent()) {// go through all the adjacent regions
								// if they're owned by the same player and they haven't been mapped yet
								if( getGroup(adj) == null && adj.isOwnedBy(owner) )
									queue.add(adj); // add them to the queue
							}
						}
					} while(!queue.isEmpty());
					curGroup = null;
				}
			}
			// get the results of test if we're testing
			if(testCapital) {
				boolean result = true;
				for(Group g: newgroups) {
					if(!g.containsCapital())
						result = false;
					groups.remove(g);
					if(!result) break;
				}
				for(Region r: regs)
					mapping[r.getId()] = this;
				return result;
			} else {
				doRecount = true;
				return false;
			}
		}
		
		/** Transfers all regions to another group. Removes the group from the GroupManager.
		 * 
		 * @param g group to transfer the regions to
		 */
		private void transferAllTo(Group g) {
			for(Region r:regs) {
				g.regs.add(r);
				mapping[r.getId()] = g;
			}
			g.capitals += capitals;
			groups.remove(this);
			g.polysNeedUpdate = true;
			g.doRecount = true;
		}
		
		/** Merges a collection of groups with this one. All the other groups get removed.
		 * 
		 * @param with the groups to merge this group with
		 */
		private void mergeWith(ArrayList<Group> with) {
			for(Group g: with)
				g.transferAllTo(this);
			polysNeedUpdate = true;
		}
		
		/** Updates the polygon list after a modification.
		 * 
		 */
		private void updatePolys() {
			polys.clear();
			for(Region r: regs)
				for(Polygon p:r.getPolygons())
					polys.add(p);
		}
		
		private void clearCount() {
			for(int i=0;i<countRscs.length;++i)
				countRscs[i] = 0;
			for(int i=0;i<countRegs.length;++i)
				countRegs[i] = 0;
			soldsPerTurn = 0;
		}
		
		private void countRegion( Region r ) {
			countRegs[r.getType().getId()]++;
			for(ResourceType rsc: r.getResources())
				countRscs[rsc.getId()]++;
		}
		
		private void recount() {
			if(!doRecount) return;
			
			doRecount = false;
			clearCount();
			
			for(Region r: regs)
				countRegion(r);
			
			for(ResourceType rsc: w.getResourceTypes())
				soldsPerTurn += rsc.getSoldiersFor(countRscs[rsc.getId()]);
			
			for(RegionType rt: w.getRegionTypes())
				if(rt.hasCombo())
					soldsPerTurn += rt.getSoldiersFor(countRegs[rt.getId()]);
		}
	}
	
	public GroupManager(World w) {
		this.w = w;
		mapping = new Group[w.getRegionCount()];
		
	}
	
	/** Gets the internal group list. Shouldn't be modified.
	 * 
	 * @return all the groups managed by this manager
	 */
	public ArrayList<Group> getGroups() { return groups; }
	
	/** Gets an internal group list of all the groups controlled by a player
	 * 
	 * @param pl owner of the groups
	 * @return the list of groups
	 */
	public ArrayList<Group> getGroups(Player pl) {
		ArrayList<Group> ret=new ArrayList<Group>();
		for(Group g: groups)
			if(g.owner == pl)
				ret.add(g);
		return ret;
	}
				
		
	/** Gets the group that contains a region.
	 * 
	 * @param r region to check
	 * @return group which contains it, or null if the group is unowned.
	 */
	public Group getGroup(Region r) { return mapping[r.getId()]; }
	
	/** Finds the groups adjacent to a region that are owned by the same player.
	 * 
	 * @param r the region to search around.
	 * @return the adjacent groups
	 */
	private ArrayList<Group> findAdjacentGroups(Region r) {
		Player pl = r.getOwner();
		ArrayList<Group> adjs = new ArrayList<Group>();
		for(Region nbr: r.getAdjacent())
			if(nbr.isOwnedBy(pl)) {
				Group gr = getGroup(nbr);
				if(gr!=null && !adjs.contains(gr))
					adjs.add(gr);
			}
				
		return adjs;
	}
	
	/** Updates the groups after the ownership of a region has changed.
	 * 
	 * @param r the region whose ownership has been changed.
	 */
	public void ownershipChanged(Region r) {
		Group startGroup = getGroup(r);
		if(startGroup !=null ) // if this region was owned by somebody else
			startGroup.remove(r);
		
		if(r.getOwner() != null ) { // if we need to add it to a group
			ArrayList<Group> adjs = findAdjacentGroups(r);
			if(adjs.isEmpty()) // if there's no other owned territory around
				new Group(r); // create a new group to accommodate the newly owned region
			else if(adjs.size()==1) // if there's only one other group
				adjs.get(0).add(r); // add the region to the group
			else { // if there's more than one we need to merge the groups that get connected by this region
				Group g = adjs.get(0);
				adjs.remove(0);
				g.add(r);
				g.mergeWith(adjs);
			}
		}
	}
	
}
